package com.zdp.leetcodeMiddle;


import com.zdp.util.TreeNode;

/*
* 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7
 

限制：
0 <= 节点个数 <= 5000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 重建二叉树_offer07 {

    /*
     * 解题思路：  根据前序 可以确定一棵树的根  利用递归
     *  将树的规模不断缩小，每次都求出他们的根
     * */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = f(preorder,inorder,0,0,inorder.length-1);
        return root;
    }
    public TreeNode f(int[] preorder,int[] inorder,int index,int left,int right){
        if(left>right){
            return null;
        }
        if(index>preorder.length-1){
            return null;
        }
        // 找到当前前序遍历的元素 在中序遍历中的位置
        //根据该位置 划分左右子树
        int mid = left;
        for(int i =left;i<=right;i++){
            if(preorder[index] == inorder[i]){
                mid = i;
                break;
            }
        }
        // 当前前序遍历元素为 根节点
        TreeNode t = new TreeNode();
        t.val = preorder[index];
        t.left = f(preorder,inorder,index+1,left,mid-1);
        // 右子树  前序是前左后右，所以 index 需要加上 左子树的个数
        t.right = f(preorder,inorder,index+1+mid-left,mid+1,right);
        return t;
    }

}
